package path;
import java.util.*;
class Graph {
    private int V; // 图中的节点数
    private LinkedList<Integer>[] adj; // 邻接表表示图的连接关系

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList<>();
        }
    }

    // 添加边，无向图
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    // BFS遍历并找到最短路径
    public List<Integer> bfsShortestPath(int start, int end) {
        boolean[] visited = new boolean[V];
        int[] parent = new int[V];

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        parent[start] = -1; // 起始节点的父节点设为-1

        while (!queue.isEmpty()) {
            int current = queue.poll();

            if (current == end) {
                return constructPath(parent, start, end);
            }

            for (int neighbor : adj[current]) {
                if (!visited[neighbor]) {
                    queue.add(neighbor);
                    visited[neighbor] = true;
                    parent[neighbor] = current;
                }
            }
        }

        return Collections.emptyList(); // 没有找到路径
    }

    // 构建路径
    private List<Integer> constructPath(int[] parent, int start, int end) {
        List<Integer> path = new ArrayList<>();
        int current = end;
        while (current != -1) {
            path.add(current);
            current = parent[current];
        }
        Collections.reverse(path);
        return path;
    }
}
public class BFS {
    public static void main(String[] args) {
        Graph graph = new Graph(7);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        int start = 0;
        int end = 6;

        List<Integer> shortestPath = graph.bfsShortestPath(start, end);

        if (!shortestPath.isEmpty()) {
            System.out.println("最短路径从节点 " + start + " 到节点 " + end + " 是：");
            for (int node : shortestPath) {
                System.out.print(node + " ");
            }
        } else {
            System.out.println("没有找到从节点 " + start + " 到节点 " + end + " 的路径。");
        }
    }
}


